The invention relates generally to encoding of digital data. In particular, the invention relates to a Viterbi convolutional decoder.
The transmission of digital data, particularly for large amounts of data over long distances, must contend with a noisy transmission path. A typical digital communication system is designed to operate at a maximum data rate and a minimum power level. These conflicting requirements usually mean that the system is operating relatively close to the noise level associated with the transmission path. As a result, a significant number of transmitted bits will be overwhelmed by the transmission path noise and will not be accurately received. That is, the bit error rate becomes unacceptably high.
Reducing the transmission rate or increasing the power levels would reduce the bit error rate. However, a more attractive alternative for many systems is to accept the high bit error rate but to provide error correction for the transmitted data. Error correction usually involves an encoder at the transmitting side of the communication path that transforms the data intended to be transmitted according to an error correction code and, necessarily, increases the number of bits to be transmitted. Then a decoder, situated at the receiving end of the transmission path, performs the inverse transformation to the one performed by the encoder. That is, the decoder operates upon the received bits and reproduces the original data. Most importantly, the decoder can use the additional information in the expanded data stream to correct bit errors up to a maximum number. The maximum number of bit errors that can be corrected depends upon the type of coding scheme used and, obviously, depends upon the extra number of transmitted bits. In the usual type of coding scheme, the transmitted bits cannot be divided neatly into data bits and correction bits because the encoder performs fairly complicated mathematical operations upon the entire data stream to produce an expanded data stream.
One type of error correction coding divides the data into regularly sized blocks which the encoder converts to a larger block. The decoder, upon receiving the encoded block, decodes it into its original form, presuming that the maximum number of bit errors has not been exceeded. Another technique, the one used in this invention, does not explicitly block the data but instead encodes or decodes the data a few bits at a time. However, the encoding and decoding depends in an indirect way on data that has already been coded. For this reason, this technique is called convolutional coding. Many types of convolutional decoders are well known. Cain, III in U.S. Pat. No. 3,662,338 discloses a threshold convolutional decoder and Forney, Jr. in U.S. Pat. No. 3,665,396 discloses a sequential convolutional decoder. Encoders for either block or convolutional codes are relatively straightforward, but decoding procedures are far more complicated because they must both perform the inverse transformation and tolerate errors. The development of practical decoding algorithms for convolutional codes has centered around probabilistic decoding algorithms on one hand and threshold or feedback decoding procedures on the other hand.
Probabilistic decoding algorithms are a type of error correction used to calculate the likelihood of the successful message transmission for all possible transmissions on the basis of reliability information extracted from present and past ensembles. The maximum probability then is the determining factor for judging what was transmitted. This approach usually involves the concept of a path of unencoded data. A possible path is defined by the sequence of unencoded data. A probabilistic decoding algorithm then calculates the probability of each path based upon both the currently received encoded data, possibly corrupted by noise, and prior receptions. At some point, the path with the highest probability is judged to be the correct path and therefore the unencoded data is determined. As a result, a memory of a suitable size for the various paths and an arithmetic capability for a message probability computation are required. Viterbi in a technical article entitled "Error Bounds for Convolutional Codes" and appearing in IEEE Transactions on Information Theory, IT-13, April 1967, at pp. 260-269, described a specific path decoding algorithm for convolutional codes which significantly reduces the number of computations needed to choose the most probable path. The theory of Viterbi decoding is well described in U.S. Pat. No. 4,015,238 to Davis and in U.S. Pat. No. 3,789,360 to Clark, Jr. et al. The Viterbi algorithm has been shown to be an efficient and practical decoding technique for short constraint length codes (to be explained later) and has been demonstrated to be a maximum-likelihood procedure.
FIG. 1 shows a relatively simple convolutional encoder in which unencoded information bits are input to a three stage shift register 20. One adder 22 receives the outputs of the three stages of the shift register 20, b.sub.2, b.sub.1 and b.sub.0 while another adder 24 receives the outputs from only the first and last stage, b.sub.2 and b.sub.0. Both the adders 22 and 24 are modulo 2 adders so that their individual outputs are 0 or 1. At each clock period, an information bit is shifted into the shift register 20 and the bits already present are shifted toward the right. Also during each clock period, the two adders 22 and 24 output their separate code. It is of course seen that one bit of input data produces two bits of output data, that is, n=1 and m=2 for a rate n/m encoder. For this reason, the encoder of FIG. 1 is called a rate 1/2 encoder.
If it is assumed that the two initial bits b.sub.0 and b.sub.1 are both set to 0, then for the next input bit b.sub.3 =0, the code symbols (0,0) are output while if b.sub.2 =1, then (1,1) is output. In the next clock period, b.sub.3 is shifted into the position of b.sub.2, b.sub.1 is substituted by b.sub.2 and b.sub.0 is substituted by b.sub.1. In this further clock period, however, the output code depends not only upon the value of b.sub.3 but also upon b.sub.2. If (b.sub.3,b.sub.2)=(0,0), then (O,O) is output in this clock period; if they equal (0,1), then (1,0) is output; if they equal (1,0), then (1,1) is output; and if they equal (1,1), then (0,1) is output. In the following clock period, the next input bit b.sub.4 is shifted into the shift register with the remaining elements being shifted right. In this and following clock periods, the values of all three elements of the shift register 20 need to be considered in order to arrive at the correct output code symbols. However, no other input bits besides those three in the shift register 20 need to be considered. Accordingly, the encoder of FIG. 1 is said to have a constraint length of 3 or k=3.
FIG. 2 shows what is commonly known as a trellis for a convolutional encoder. The encircled numbers are the encoder states, that is the last two bits in the register 20, shown as b.sub.1 and b.sub.0 in FIG. 1. The paths from an encoder state are illustrated as solid when the next input bit, b.sub.2 in FIG. 1, is a 0 and illustrated as dashed when the input bit is 1. Also shown enclosed in circles in FIG. 2 are the code symbols that are output from the adders 22 and 24, dependent not only upon the most recent input bit but also upon the state of the next two older bits. The initial encoder state at a depth of zero, as mentioned previously, is assumed to be (O,O), so that at the next depth of the trellis, there are two possible encoder states (O,O) and (1,0). At a trellis depth of 2, there are four possible encoder states, each reachable by only a single path for combinations of (b.sub.3,b.sub.2). What has been described to this point is simply a decisional tree. However, at a trellis depth of 3, there are again only four encoder states, each reachable by one of two paths. For instance, the encoder state (0,0) at trellis depth of 3 could be reached from an immediately prior encoder state of (0,0) with an input bit of 0 or from an encoder state of (0,1), also with an input bit of 0. The trellis pattern is repeated at each trellis depth greater than 3 for an encoder a constraint length of 3 encoder. The trellis diagram of FIG. 2 is important in convolutional decoders because it has been folded back to form a limited number of encoder states, four in FIG. 2, and the encoder states combined with the most recent input bit, constitute the total number of bits that need to be considered in the initial step of decoding.
The trellis diagram is used in decoding in the following manner. Only one path, defined by the sequence of input bits, is allowed to survive to any given encoder state at each trellis depth but there will be four surviving paths passing each trellis depth greater than the trellis depth of 2. When the next two-bit code symbol is received, the possible paths to the next trellis depth are used to generate tentative code symbols that can be compared with the received code symbol for the extension of the trellis to the new trellis depth. For each of the possible paths into one new encoder state, a probability is calculated as to whether that path had generated the current code symbol. Only the one path with the highest probability leading to that encoder state is allowed to survive. Thus it is seen that the surviving paths can cross, can branch and can become extinct, but always there are four surviving paths at each depth of the trellis.
Rather than calculate the probability that a particular path produced a particular sequence of received symbols, it is common to instead calculate the metric, which is a measure of the distance between the code symbols the path produced and the actually received code symbols. The minimum metric corresponds to the maximum probability. In the case where a hard decision is made on the received code symbols such that either one or the other of the two values of the bits in the code symbol is judged to have been received, then the metric is the number of differences between the received code symbols and the code symbols resulting from the path being evaluated. The advantage of using the metric is that, at each depth of the trellis, the metric is updated according to the most recently received symbols and it is not necessary to recompute the metric of the entire path.
In theory, the path histories for the entire transmission need to be maintained and only at the end of the transmission is the metric minimized to determine the path with the highest probability. This high probability path would then determine the entire transmission. However, in practice, once path histories for 4 or 5 constraint lengths have been calculated, it is highly likely that the oldest parts of the paths satisfactorily determine the input bits. This is explained by Viterbi in an article entitled "Convolutional Codes and Their Performance in Communication Systems", appearing in IEEE Transactions on Communication Technology, Vol. COM-19, No. 5, October 1971. Because of this fact, path histories are generally held in memory for only 4 or 5 constraint lengths and the oldest values are used as the result of the decoding.
It is seen that the decoder is very amenable to parallel design and processing since parallel paths through a multiplicity of encoder states must be calculated at each trellis depth. Parallel implementations are used by Davis and by Clark, Jr. et al in the previously cited patents. A parallel design appears to be implicit in the Viterbi decoders of Doland (U.S. Pat. No. 4,240,156) and Low et al (U.S. Pat. No. 3,697,950) who disclose the hardware for only one path. Obviously, parallel processing provides relatively high speed processors, perhaps with additional complexity due to the need for common metric and path memories. It must be borne in mind, however, that the rate 1/2 encoder, shown in FIG. 1, was presented for its ease of presentation. In fact, there are advantages to operating with longer constraint lengths. The number of encoder states, and thus the number of parallel processors in a parallel design, is 2.sup.k-n, that is, an exponential function of the constraint length less the information bits per input state. For the Viterbi decoders to be described with this invention, there are 64 encoder states. Such a decoder may be very fast but its complexity becomes a limiting factor. For low-cost, low-data rate commercial digital earth stations, for use with satellite communication systems, the complexity of the parallel processing for Viterbi decoding has meant that the decoder hardware has not been available. Ironically, it is precisely in these low-cost stations that the potential coding gain achievable in the Viterbi decoding is most needed. Attempts to reduce the complexity of the individual elements for the parallel processors have compromised the path memory and constraint lengths of the preferred code.